/**
 * 矩阵类:适合存储稀疏矩阵
 *
 * @author wt
 */
public class Matrix implements IMatrix {
    Node<Integer>[] datas; // 三元组表
    private int m, n, t; // m行,n列,t个非零元素

    /**
     * @param m 行数
     * @param n 列数
     * @param t 非零元素个数
     */
    private Matrix(int m, int n, int t) {
        this.m = m;
        this.n = n;
        this.t = t;
        datas = new Node[t];
    }

    /**
     * @param matrix 以二维数组存储的矩阵
     */
    public Matrix(Integer[][] matrix) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        int num = 0;

        // 统计二维数组中非零元个数
        for (int i = 0; i < this.m; i++) {
            for (int j = 0; j < this.n; j++) {
                if (matrix[i][j] != 0) {
                    this.t++;
                }
            }
        }

        // 以非零元个数来初始化三元组表
        datas = new Node[this.t];

        // 给三元组表赋值
        for (int i = 0; i < this.m; i++) {
            for (int j = 0; j < this.n; j++) {
                if (matrix[i][j] != 0) {
                    this.datas[num] = new Node<>(i, j, matrix[i][j]);
                    num++;
                }
            }
        }
    }

    public void showMatrix() {
        boolean isZero = true;
        System.out.println("行数,列数,非零元素个数:" + this.m + "," + this.n + "," + this.t);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < t; k++) {
                    if (i == datas[k].row && j == datas[k].col) {
                        isZero = false;
                        int value = datas[k].value.intValue();
                        if (value < 0 || value > 9) {
                            System.out.print(value + "    ");
                        } else {
                            System.out.print(value + "      ");
                        }
                        break; // 提高效率(可不加)
                    }
                }
                if (isZero) {
                    System.out.print(0 + "     ");
                }
                isZero = true;
            }
            System.out.println();
        }

    }

    public void showTriples() {
        System.out.print("当前矩阵的三元组表为(行,列,值):");
        for (int i = 0; i < datas.length; i++) {
            System.out.print(this.datas[i].toString() + " ");
        }
        System.out.println("");
    }

    public Matrix fastTransposeMatrix() {
        Matrix newMatrix = new Matrix(this.n, this.m, this.t);
        // 定义并初始化一个统计数组(统计转前每列中非零元素个数)
        int num[] = new int[n];
        for (int col = 0; col < n; col++) {
            num[col] = 0;
        }
        // 统计转前每列中非零元素个数
        for (int i = 0; i < t; i++) {
            num[this.datas[i].col]++;
        }
        // 快速定位数组(转前三元组中元素在转后新三元组中的位置)
        int cpot[] = new int[n];
        cpot[0] = 0; // 转前列号=0的第一个非零元,在转后新三元组表中也一定是第一个
        for (int col = 1; col < n; col++) { // 计算每列中第一个非零元素在转后新三元组中的位置(数组下标)
            cpot[col] = cpot[col - 1] + num[col - 1];
        }
        // 遍历一次转前三元组表,同时实现转置
        for (int i = 0; i < t; i++) {
            int col = this.datas[i].col;
            int newPos = cpot[col];
            // 完成转置
            newMatrix.datas[newPos] = new Node<>();
            newMatrix.datas[newPos].row = this.datas[i].col;
            newMatrix.datas[newPos].col = this.datas[i].row;
            newMatrix.datas[newPos].value = this.datas[i].value;
            // 转前col列下一个非零元素,在转后三元组表中位置
            cpot[col]++;
        }
        return newMatrix;
    }
}
